1. Field of the Invention
This invention relates generally to search, and in particular to data structures used for indexing items and matching search queries for incremental searching in a desktop environment.
2. Background of the Invention
The typical desktop environment contains a wide variety of information and information sources. A user must select among different interfaces to locate, then access each type of information, for instance by launching a browser to obtain networked information, selecting an application to launch through a start menu, or drilling down among folders for a document or other type of file. There is no single interface for accessing all of these different types of content, placing the burden on the user to search separately for them or to remember specific desktop pathways.
A unified desktop search application could be used to address these problems. Among other possibilities, it would be desirable for a user to be able to access applications, desktop files, and/or data on local or networked servers through a single interface. Access to each of these could be initiated by finding and identifying the correct resource, through the user's selection of a search result. Search results should be generated using methods that reflect how desktop resources are used. In most cases, the most relevant items are likely to be those that have been accessed or used recently and frequently, or have been designated as particularly important by the user, for instance through the creation of a desktop shortcut.
One way to generate a search result based on desktop data is to index the data according to a relevance score, locate data in the index that matches the search string, and provide the result in relative score order. Each step in the process, from generating and updating the index to returning a scored result, consumes read-write cycles, computer memory, and processing resources in amounts that vary depending on system implementation. As a process likely to be run repeatedly throughout the course of a computing session, querying must both be accurate and fast, consuming the minimal amount of resources needed to generate correct results. At the same time, it should be possible to update the data index in real time, as changes in desktop contents occur, with little impact on system performance. It would also be particularly desirable to display incremental search results as a user enters a search string (i.e. carry out prefix searching), in order to save the trouble of entering an entire query. The need for querying efficiency is particularly great in the context of incremental searching since query results are generated not only once, but with each additional character of a search term. For content searching, which is commonly performed in desktop environments, it would be useful to also be able to perform full-text searches that tend to generate more comprehensive results.
What are needed, therefore, are methods-of scoring, indexing, and querying items that consume a minimal amount of system resources, generate accurate query results, and support incremental searching.